
public class MySingleList implements IList{

    static class LinkedNode{
        public int value;
        public LinkedNode next;

        public LinkedNode(int value) {
            this.value = value;
        }

    }
    LinkedNode node6 = new LinkedNode(12);

    public LinkedNode head;
    public LinkedNode removeElements(LinkedNode head, int val) {
        if(head == null) {
            return null;
        }
        LinkedNode prev = head;
        LinkedNode cur = head.next;
        while(cur != null) {
            if(cur.value == val) {
                prev.next = cur.next;
            }else {
                prev = cur;
            }
            cur = cur.next;
        }
        if(head.value == val) {
            head = head.next;
        }
        return head;

    }
    public LinkedNode reverseList(LinkedNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        LinkedNode cur = head.next;
        head.next = null;
        while(cur != null) {
            LinkedNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    public LinkedNode middleNode(LinkedNode head) {
        if(head == null) {
            return null;
        }
        LinkedNode fast = head;
        LinkedNode slow = head;
        //下面的fast.next != null && fast != null前后两个条件不能调换，否则会出现空指针异常
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public LinkedNode partition(int x) {
        //小于x的区间
        LinkedNode bs = null; //始终不动的在第一区间的开头
        LinkedNode be = null;

        //大于等于x的区间
        LinkedNode as = null; //始终不动的在第二区间的开头
        LinkedNode ae = null;

        LinkedNode cur = head;
        while(cur != null) {
            if(cur.value < x) {
                if (null == bs) {
                    //第一区间如果没有值的话，就插入一个元数
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if(null == as) {
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //如果第一个区间为null则be.next会出现指针异常；
        if(be == null) {
            return as;
        }
        //第一个1区间有数据
        if(ae != null) {
            //第二个区间有数据，但可能它的指针域不为null
            ae.next = null;
        }
        be.next = as;
        return bs;
    }


    public static LinkedNode getIntersectionNode(LinkedNode headA, LinkedNode headB) {
        LinkedNode nl = headA;
        LinkedNode ns = headB;

        int len1 = 0;
        int len2 = 0;
        while(nl != null) {
            len1++;
            nl = nl.next;
        }
        while(ns != null) {
            len2++;
            ns = ns.next;
        }
        ns = headB;
        nl = headA;
        int len = len1 - len2;
        if(len < 0) {
            nl = headB;
            ns = headA;
            len = len2 - len1;
        }
        //保证了nl放的是长的链表，ns里面放的是短的链表，len的值是大于0的

        while(len != 0) {
            len--;
            nl = nl.next;
        }

        while(ns != nl) {
            nl = nl.next;
            ns = ns.next;
        }
        if(nl == null) {
            return null;
        }
        return ns;

//        LinkedNode cur1 = headA;
//        LinkedNode cur2 = headB;
//        int len1 = 0;
//        int len2 = 0;
//        while (cur1 != null) {
//            len1++;
//            cur1 = cur1.next;
//        }
//        while (cur2 != null) {
//            len2++;
//            cur2 = cur2.next;
//        }
//        while (cur1 != null && cur2 != null) {
//            cur1 = cur1.next;
//            cur2 = cur2.next;
//        }
//        int len = 0;
//        cur1 = headA;
//        cur2 = headB;
//        if (cur1 == null) {
//            //cur1为短
//            len = len2 - len1;
//            while (len != 0) {
//                len--;
//                cur2 = cur2.next;
//            }
//        } else {
//            //cur2为短
//            len = len1 - len2;
//            while (len != 0) {
//                len--;
//                cur1 = cur1.next;
//            }
//        }
//        while (cur1 != cur2) {
//            cur1 = cur1.next;
//            cur2 = cur2.next;
//        }
//        if (cur1 == null) {
//            return null;
//        }
//        return cur1;
    }

    //判断是否有环

    public boolean hasCycle(LinkedNode head) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast != null && fast.next != null) {
            return false;
        }
        return true;
    }
    //返回倒数第k个元素
    public int retTOValue(int k) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        if(k < 0) {
            return 0;
        }
        int count = 0;
        while((k-1) != count) {
            count++;
            if(fast.next == null) {
                return 0;
            }
            fast = fast.next;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.value;
    }
    public LinkedNode mergeTwoLists(LinkedNode list1, LinkedNode list2) {
        LinkedNode newh = new LinkedNode(-1);
        LinkedNode tmph = newh;
        if(list1 == null || list2 == null) {
            return null;
        }
        while(list1 != null && list2 != null) {
            if(list1.value < list2.value) {
                tmph.next = list1;
                list1 = list1.next;
            }else {
                tmph.next = list2;
                list2 = list2.next;
            }
            tmph = tmph.next;
        }
        while(list1 != null) {
            list1 = list1.next;
        }
        while(list2 != null) {
            list2 = list2.next;
        }
        return newh;

    }
    public boolean chkPalindrome(LinkedNode A) {
        //找中间结点
        LinkedNode fast = head;
        LinkedNode slow = head;
        while(fast.next != null && fast != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //从中间位置开始翻转
        LinkedNode cur = slow.next;
        while(cur != null) {
            LinkedNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //开始回文
        while(slow != head) {
            if(slow.value != head.value) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            slow = slow.next;
            head =  head.next;
        }
        return true;
    }
    public void setNode() {
        LinkedNode node1 = new LinkedNode(12);
        LinkedNode node2 = new LinkedNode(78);
        LinkedNode node3 = new LinkedNode(34);
        LinkedNode node4 = new LinkedNode(68);
        LinkedNode node5 = new LinkedNode(55);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }


    @Override
    public void addFirst(int data) {
        LinkedNode node = new LinkedNode(data);
        if(this.head == null) {
            head = node;
        }else {
            node.next = head;
            head = node;
        }
    }

    @Override
    public void addLast(int data) {
        LinkedNode node = new LinkedNode(data);
        LinkedNode cur = head;
        if(this.head == null) {
            head = node;
        }else {
            while(cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    public LinkedNode preIndex(int index) {
        LinkedNode cur = head;
        while((index-1) != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    @Override
    public void addIndex(int index, int data) {
        LinkedNode node = new LinkedNode(data);
        if(index < 0 || index > size()) {
            throw new RuntimeException("位置异常！" + index);
        }
        if(index == 0) {
            addFirst(data);
        }else if(index == size()) {
            addLast(data);
        }else {
            LinkedNode cur = preIndex(index);
            node.next = cur.next;
            cur.next = node;
        }

    }

    @Override
    public boolean contains(int key) {
        if(this.head == null) {
            return  false;
        }else {
            LinkedNode cur = head;
            while(cur != null) {
                if(cur.value == key) {
                    return true;
                }
                cur = cur.next;
            }
        }
        return false;
    }

    public LinkedNode removeKey(int key) {
        if(this.head == null) {
            return null;
        }
        LinkedNode del = head;
        while(del != null) {
            if(del.value == key) {
                return del;
            }
            del = del.next;
        }
        return null;
    }
    public int retNum(int key) {
        int count = 0;
        LinkedNode cur = head;
        while(cur != null) {
            if(cur.value == key) {
                return count;
            }
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public void remove(int key) {
        if(removeKey(key) == null) {
            System.out.println("没找到要删除的数据！！");
        }else {
            int count = retNum(key);
            LinkedNode del = removeKey(key);
            LinkedNode cur = head;
            while(cur != null && count != 0) {
                if(cur.next.value == key) {
                    cur.next = del.next;
                    return;
                }
                cur = cur.next;
            }
            head = head.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        LinkedNode prev = head;
        LinkedNode cur = head.next;
        while(cur != null) {
            if(cur.value == key) {
                prev.next = cur.next;
            }else {
                prev = cur;
            }
            cur = cur.next;
        }
        if(this.head.value == key) {
            head = head.next;
        }
    }

    @Override
    public int size() {
        if(this.head == null) {
            return 0;
        }else {
            int count = 0;
            LinkedNode cur = head;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }
    }

    @Override
    public void clear() {
        LinkedNode cur = head;
        while(cur != null) {
            LinkedNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
    }

    @Override
    public void display() {
        LinkedNode cur = head;
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
